#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <string.h>

void PrintArray(int* a, int n);
// 排序实现的接口
 
// 插入排序
void InsertSort(int* a, int n);
 
// 希尔排序
void ShellSort(int* a, int n);
 
// 选择排序
void SelectSort(int* a, int n);
 
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
 
// 冒泡排序
void BubbleSort(int* a, int n);
 
// 快速排序递归实现
 
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
 
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
 
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int begin, int end);
 
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right);
 
// 归并排序递归实现
void MergeSort(int* a, int n);
 
// 归并排序非递归实现
void MergeSortNonR(int* a, int n);
 
// 计数排序
void CountSort(int* a, int n);


typedef int STDatatype;
typedef struct Stack
{
    STDatatype* a; //动态开辟的空间
    int top; //栈顶
    int capacicy; //容量
}ST;

void StackInit(ST* ps);//初始化
void StackPush(ST* ps, STDatatype x);//插入
bool StackEmpty(ST* ps);//判空
void StackPop(ST* ps);//删除
STDatatype StackTop(ST* ps);//栈顶
int StackSize(ST* ps);//长度
void StackDestory(ST* ps);//销毁
